package example5;

import java.util.ArrayList;
import java.util.List;

//448. 找到所有数组中消失的数字
public class LeetCode448 {
    public static void main(String[] args) {

    }
}

/**
 * 方法二：优化的hash，将原有的nums当作hash，i+1是否存在的标识存储在nums[i]中。
 * 因为nums中的所有数都在[1,n]之间，所以如果num存在，那么就让nums[num-1] += n。
 * 所以在后面判断的时候，如果nums[i] > n，那么说明i存在。
 *
 * 在第一遍遍历标记存在和不存在的数时，遍历到nums[i]时，这个位置的数有两层含义，
 * 一是当前位置最开始存储的数[1,n]之间，另一次是表示当前i+1这个数是否存在，
 * 如果存在的话，那么说明在i之前已经找到了，那么就会将nums[i] + n。
 *
 * 所以，如果nums[i] > n的话说明i+1一定存在，因为最初时每个数只能取[1,n]。
 * <= n时说明i+1不存在，也不用担心等于n的特殊情况，因为最初只能取[1,n]，
 * 所以如果i+1存在，那么nums[i]一定大于n。所以如果 nums[i] == n，说明i+1不存在，且n一定存在。
 * 同时将nums[n-1] += n。
 *
 * 所以第一遍遍历到nums[i]时，它会存储原本的数和i+1的表示，要知道原本的数，就可以通过(nums[i]-1) % n得到原本数的下标，
 * 设(nums[i]-1) % n为x，将nums[x] += n。这样第一遍遍历结束后就将所有数进行了标识。
 * 第二遍遍历的时候，如果nums[i] > n，说明i+1存在。
 */
class Solution448_2 {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> list = new ArrayList<>();
        int n = nums.length;
        for(int num : nums){
            int x = (num - 1) % n;
            if(nums[x] <= n){
                nums[x] += n;
            }
        }
        for(int i=0;i<n;i++){
            if(nums[i] <= n)    list.add(i+1);
        }
        return list;
    }
}

/**
 * 方法一：hash
 */
class Solution448_1 {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        int n = nums.length;
        int[] arr = new int[n];
        List<Integer> list = new ArrayList<>();
        for(int i=0;i<n;i++){
            if(arr[nums[i]-1] == 0) arr[nums[i]-1] = 1;
        }
        for(int i=0;i<n;i++){
            if(arr[i] == 0) list.add(i+1);
        }
        return list;
    }
}
